#include "linktree.h"
#include <iostream>
TreeNode::TreeNode(const ElementType &date) : date(date)
{
    parent = firstchild = nextSbling = nullptr;
}

void TreeNode::Connect(TreeNode *parent)
{
    if (!parent)
        return;
    this->parent = parent;
    // 头插
    this->nextSbling = parent->firstchild;
    parent->firstchild = this;
}

void TreeNode::DisConnect(TreeNode *parent)
{
    if (parent == nullptr || this->parent!=parent)
    {
        return;
    }
    TreeNode *TP = parent->firstchild;
    if (this == parent->firstchild)
    {
        parent->firstchild = this->nextSbling;
        
    }
    else
    {
        while (TP->nextSbling != nullptr)
        {
            if (TP->nextSbling == this)
            {
                TP->nextSbling = this->nextSbling;
               
                break;
            }
            TP = TP->nextSbling;
        }
    }
    
    parent=nextSbling = nullptr;
}

void TreeNode::show(TreeNode *node, int n)
{
    if (node == nullptr)
    {
        return;
    }
    if (node->parent != nullptr)
    {
        for (int i = 0; i < n; i++)
        {
            std::cout << "  ";
        }
        std::cout << "|-" << node->date << std::endl;
    }
    show(node->firstchild, n + 1);
    show(node->nextSbling, n);
}

void TreeNode::FreeNode(TreeNode *node)
{
    if (node == nullptr)
    {
        return;
    }
    FreeNode(node->firstchild);
    FreeNode(node->nextSbling);
    delete node;
}

void TreeNode::FindByElement(TreeNode *node, const ElementType &element,DARRAY::DynamicArray&a)
{
    if (node == nullptr)
        return ;
    if (node->date == element&&node->parent!=nullptr)
        {
            a.InsertTail(node);
        }
    FindByElement(node->firstchild, element,a);
    FindByElement(node->nextSbling, element,a);
    
}

int TreeNode::GetNodeHight(TreeNode *node)
{   int maxhight=0;
    if (node==nullptr)
    {
        return 0 ;
    }
    //找最高的子树
    TreeNode*TP=node->firstchild;
    while (TP!=nullptr)
    {
        int hight =GetNodeHight(TP);
        maxhight=maxhight>hight?maxhight:hight;
        TP=TP->nextSbling;
    }
    
    return maxhight+1;
}

TreeNode *TreeNode::Getparent()
{
    return parent;
}

std::string &TreeNode::GetDate()
{
    return date;
}


    




LinkTree::LinkTree()
{
    root = new TreeNode("");
}

LinkTree::LinkTree(const ElementType &element)
{
    root=new TreeNode(element);
}

LinkTree::~LinkTree()
{

    TreeNode::FreeNode(root);
}

TreeNode *LinkTree::GetRoot()
{
    return root;
}

void LinkTree::show()
{
    root->show(root, 0);
}

DARRAY::DynamicArray LinkTree::FindByElement(const ElementType &element)
{
    DARRAY::DynamicArray a;
    TreeNode::FindByElement(root,element,a);
    return a;
}

int LinkTree::GetTreeHight()
{

    return TreeNode::GetNodeHight(root)-1;
}

std::string LinkTree::GetNodePath(TreeNode *node)
{   
    if (node==nullptr)
    {
        return std::string();
    }
    std::string path=node->GetDate();
    while(node->Getparent()!=nullptr)
    {
        path=node->Getparent()->GetDate()+"/"+path;
        node=node->Getparent();
   }
   return path;
}


